package com.fanco.learn_datastruct_leetcode.searchmethods;

/**
 * Java 实现二分查找的 Demo
 * 二分查找 顾名思义 将有序数组一分为二进行查找，如果中间数 > 查找数 则从左边查询
 *
 * 二分查找需要确保有序，并且只能是数组
 * @author qiaowang 2021/7/20
 */
public class BinarySearchDemo {
    public static void main(String[] args) {
        int[] a = {1, 3, 5, 7, 9, 11};
        int target = binarySearch(a, 7);
        System.out.println(target);

    }

    public static int binarySearch(int a[], int key) {
        int low = 0;
        int high = a.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a[mid] > key) {
                high = mid - 1;
            } else if (a[mid] < key) {
                low = mid + 1;
            } else {
                return a[mid];
            }
        }
        return -1;
    }
}
